perm filename PROP[P,JRA]1 blob
sn#163296 filedate 1975-06-10 generic text, type T, neo UTF8
We believe that the current approaches to programming as taught in
most universities are woefully inadequate. Students are taught to
become fluent in the mechanical skills of coding but are not given
the intellectual understanding of problem-solving through algorithms.
Even where the courses have been revised, the students are usually
required to present the program to the machine in the traditional
manner: a completed program, fully thought-out and ready to run. We
believe that the best ways to correct the situation is to develop
texts which teach problem solving in the context of programming and
simultaneously develop programming tools which will reinforce the
skills taught in the classroom. The language addressed in this
proposal is LISP and the content of this proposal is the development
of a workshop for LISP programming. Before presenting the technical
details, we will justify the choice of LISP.
One of the most important concepts which should be developed in a
programming course is that of abstractions; both in the
representation of the algorithms and in the data. We must allow
students to formulate their solutions in as natural a setting as
possible. When they want to formulate algorithms dealing with sets,
they should not be forced to think immediately of a representation of
a set. All they should need to explain are the structural properties
of sets: their constructors, selectors and recognizers.
Similarly when thinking about the algorithm the student should think
structurally about its flow of control: it's a recursion, or an
iteration, or a sequence of operations.
A LISP text [Allen] has been developed which is addressed to exactly
this methodology. The text develops LISP as a language for
discussing abstract algorithms and data structures and stresses the
importance of representation.
Certainly if we teach this approach in the classroom, we must develop
tools of similar character so that the students can write their
programs. It is ineffectual to require that the student approach the
machine with a completely specified program. Certainly when we wish
to run the program all parts of the algorithm must be specified and
specific representations must be given of the data structures, but
the creative part of programming is discovery phase and we must help
the students at this level. This proposal describes an initial set
of tools for such an endeavor.
What should be done in the CAI workshop.
1. supply tools for construction of algorithms. The classroom
description of the formulation of the algorithms and data structures
must be reflected in the devices available to the student. "It's a
recursion on a data structure named polynomial -- it's a conditional
expression...". That is we want to describe our algorithms in terms
of structure of the data and algorithm, with as little concrete
syntax as possible. -- recursion, is recursion, regardless of the
concrete syntax of the language-- just as our conceptions of abstract data structure
take different forms depending on the representation we happen to
take.
2. Supply tools for discovery of algorithms. When we begin the
construction of an algorithm --particularly if it is complex -- we
are not completely sure of all the details of the control structure
or details of the data structures. We would like to be able to begin
addressing the machine with the information we do know and as we
formulate the problem, be able to return to prior stages of
development -- a structural backspace, if you wish-- to reformulate
our conception of a data structure or piece of the algorithm.
3.Once we have completed that abstract algorithm, we need facilities
to map it onto a running LISP program. We need to pick
representations for abstract data structures, we need to map the
algorithm onto the s-expression representation. The second task is
quite mechanical and can therefore be done automatically. The first
task requires some interaction with the user.
We will now give the outline of an on-line session showing
the basic flavor of the proposed language for describing algorithms.
The actual commands of the language will of course be determined
by experience and experiment.
The important idea is to supply commands which are as close as
possible to the way we think about writing algorithms and describing
data structures.
A session to develop an algorithm for differentiation:
In the following "s:" stands for "student".
s:(thinks) want binary recursive alg named diff, recursive on x.
(types) R diff[x;y]; R=recursion
----------displays
diff <= λ[[x;y]E]
------------
notes: 1. The material: "_______display
...
__________" is what the user will see in the display.
2. Though nothing explicity appears to the effect that "diff" is
recursive, the system will be building up information about
algorithms and data structures. Thus if it detects inconsistencies
during the construction phase it can notify the user.
3. Besides recurison, we also supply a template for iteration in the
form of a "while" expression.
s: (thinks) recursive on x which is a structure named exp;
and y is a representation of a "variable".
(types) T x:exp, y:var; T=type
-----------displays
diff <= λ[[x:exp;y:var]E]
--------------
notes: 1.If it knows constructors, selectors and recognizers for "exp"
then it can help fill in the body of E, when at the next stage
we tell it that "E" is a conditional expression. Regardless, by
time we are finished, it will know all about "exp".
s: (th) E is a conditional expression, where the predicates are recognizers
on structure of x.
(ty) CO E,x; CO=conditional
----------disp
diff <= λ[[x:exp;y:var][p1→e1; ...]
---------
note: 1. if the structure of exp were known, the pi-recognizers could be
supplied by the machine.
s: (th) recognizes the significance of the above note, and instead
of explicitly stating each recognizer for the elements of exp,
decides to begin characterizing exp.
(ty) REC exp is_var, is_const, is_sum; REC=recognizers
-------disp
diff <= λ[[x:exp;y:var][is_var[x] → e1;
is_const[x] → e2;
is_sum[x] → e3;
]
_________
note: 1.alternatively the user could begin selective specification of the
pi's (as we will now do in e1).
s: (th) The derivative of variable is either 0 or 1, depending on second
parameter, y.
(ty) CO e1; CO=conditional
-------disp
diff <= λ[[x:exp;y:var][is_var[x] → [p11→e11; ...]
is_const[x] → e2;
is_sum[x] → e3;
]
_________
s: (th) finish off e1.
(ty) p11: x=y; e11: 1; p12: T; e12;
-------disp
diff <= λ[[x:exp;y:var][is_var[x] → [x=y → 1;
T → 0]
is_const[x] → e2;
is_sum[x] → e3;
]
_________
notes: 1. the system can do some type-checking on x=y, with what it
now knows about x, y, and =.
2. the system is also starting to catalog information about the
output of diff.
s: (th) e2 is easy. do it.
(ty) e2: 0;
-------disp
diff <= λ[[x:exp;y:var][is_var[x] → [x=y → 1;
T → 0]
is_const[x] → 0;
is_sum[x] → e3;
]
_________
s: (th) e3 is to be a representation of the sum of the derivatives.
(ty) CTR sum: mk_sum[exp;exp]exp; CTR=constructor
(ty) e3: CTR sum;
-------disp
diff <= λ[[x:exp;y:var][is_var[x] → [x=y → 1;
T → 0]
is_const[x] → 0;
is_sum[x] → mk_sum[a1;a2];
]
_________
s: (th) a1 and a2 are computations on the selectors of the components
of x.
(ty) SEL sum: arg1[exp], arg2[exp]; SEL=selector
(ty) a1:diff[arg1[x];y], a2:diff[arg2[x];y];
-------disp
diff <= λ[[x:exp;y:var][is_var[x] → [x=y → 1;
T → 0];
is_const[x] → 0;
is_sum[x] → mk_sum[diff[arg1[x];y]
diff[arg2[x];y]];
]
_________
Now we have specified the high level representation of the algorithm.
Here is the transcript of the session:
R diff[x;y]
TY x:exp, y:var;
CO E,x;
REC exp is_var, is_const, is_sum;
CO e1;
p11: x=y; e11: 1; p12: T; e12;
e2: 0;
CTR sum: mk_sum[exp;exp]exp
e3: mk_sum;
SEL sum: arg1[exp], arg2[exp];
a1:diff[arg1[x];y], a2:diff[arg2[x];y];
We need to specify representations for the data structures before the
algorithm can be run. Obviously the dialect of LISP which we have
used would have to be mapped to an S-expression representation before
it would run; this map is a mechanical process.
Again, the actual command language has not been fixed, it is the
ideas and the approach that is important. Several other ideas come to
mind immediately. The approach to abstract algorithms which we are
describing is not slanted towards just beginning students. We sees
this as a viable tool for all classes of users. But given these
general techniques for creation of LISP algorithms, it is quite
reasonable to start developing aids for students. (a) since the
student is developing the algorithm structurally, rather than as a
string of characters, we can more easily monitor the students train
of thought. Particularly if the student is working on a known
problem, we can get a handle on his progress without having to read
his mind. Thus prompting and suggestions could be given. Notice
that consistency checking of things like types and function calls are
always available to any user.
(b)transcripts of programming sessions, perhaps augmented with text,
can be "played back" by the student on the display --similar to
playing chess games from a book--.
The programs can be run on the standard LISP environment, but when
errors are discovered, the user should return to the "transcript" and
make appropriate modifications there. This way we can retain tight
control of the program development, and the transcript is always an
accurate description of the program's history.
The ideas presented in this proposal have many ancestors. The
initial inquiry comes for our experience with display-based
programming. It is clear that there are tasks which are quite
manageable on sophisticated displays but which are not possbile to do
well or at all on other consoles. We began thinking about what was
the essential difference.
From many years of teaching LISP we have developed a blackboard style
which is very effective in communicating algorithms and the problems
of representations. We began thinking about how to turn this style
into a tool for writing programs.
At the same time the problems of helping people write correct
programs has been the subject of much of our current research. We now
believe that the root of the problem is poor quality of education and
poor tools available to the programmer. The tools we are advocating
involve interactive programming.
Unfortunately "interactive programming" means too many things.
Programming aids varying from clever spelling correctors to
sophisticated editing and debugging tools are all within the
terminology. We claim that ours is a more fundamental interpretation
of the phrase.
On-line editing and debugging aids are now quite common-place. We
should look carefully at the best of these and see what essential
features can be applied to program construction.
The best editing facilities derive from TVEDIT and its dialects. This
editor is display-based and allows the user to access text files in
pages like a book. The editing commands give the ability to insert
arbitrary text within a page; to shrink a page by deletion or to edit
existing lines. What makes these editors superior is that the
display window always reflects the state of the user's manuscript in
a natural format. When text is inserted the portion of the screen
below the insertion is moved down; when lines are deleted, the
succeeding text is moved up. When corrections are made the old text
is overwritten on the screen. Those who are familiar with such
editors would rather compose text on-line rather than write out the
ideas on paper and then repeatedly rewrite sections until an
acceptable product is arrived at.
There is the sophisticated display-based debugging program named
RAID. It allows the user to monitor the execution of his machine
language program displaying the contents of selected registers. As
the contents of these locations change, the user sees this effect. He
has commands at his disposal for stepping through his program;
examining locations; for halting execution in the case certain
conditions occur. Again people who have used such debugging
techniques would not consider looking at memory dumps. Lately several
researchers have begun to apply display-based techniques to the
debugging of programs written in higher-level languages. One of the
essential ingredient in these successful programs is that of
naturalness of expression. The user is able to think and react more
in his terms than in those convenient to the machine. The display
devices play a crucial role by giving the user a lot of pertinent
information all at once. We should begin thinking of analogous
systems for the professional programmer.
What is analogous to "naturalness" in the realm of program
construction? We believe it is closely related to what D. Swinehart
call "manipulative activities" as compared to "symbolic activities".
As an example of "manipulative activity" he notes that in playing a
musical instrument one does not think in terms of plucking strings or
pushing keys, but thinks in terms of producing notes or melodic
phrases. Swinehart initiates a study of some computational activities
with an eye toward producing commands simple and natural enough that
while doing them we need think only in terms of their effect. "In
this way they [the commands] tend to lose any symbolic meaning and
tend to become practically bodily extensions." In the domain we are
examining, that of program construction, we would expect to be able
to manipulate program constructs in a manner as close as possible to
the way in which we think. We think of loops, or recursion, or
assignment; we think structurally. To exploit our analogy with music
again: in playing the piano we need to recognize which key should be
selected to produce the desired note. Using a stringed instrument, we
have more responsibility; we have to locate the proper position on
the fingerboard; frets simplify the situation somewhat, but the
mechanics of producing music is still more complicated. In computer
science, the "compositions" we wish to write are programs. What we
are advocating here is that we do our composition by selecting the
"notes" --the programming constructs--, rather than being forced to
construct each "note" from symbols.
Current editors, like TVEDIT, are thus oriented toward "symbolic
activities". They work as well for document preparation as for
program preparation, even though the tasks are quite distinct. Few
of us still think in a text-oriented card image fashion when
describing programs. We think in terms of the structure of either
the program or the data. We we propose is to give critical
examination to the process of program construction with the aim of
producing a language for constructing algorithms.
Thus we became interested in developing a command language for
construction and manipulation of programs. The output from such a
session is to be an algorithm, described in a specification language
whose components are rich enough that a very large class of
data-structure manipulating algorithms can be naturally described.
At the most concrete level we need a "structural editor" This
"editor" which is controlled by structural requests, rather than by
strings.
Fred Hansen demonstrated the feasibility of such an editing scheme in
his EMILY system. There he used a formalism like BNF to describe the
syntax rules of a language. The programmer, sitting at a display
console, was presented with a "menu" of syntax equations. He could
then select instances of these rules, building up a syntax tree. He
could thus replace any of the non-terminal nodes on this syntax tree
using elements in the menu. As a result of this systematic
construction, the program was always guaranteed to be syntactically
well-formed. For us, the essential ingredient of his scheme was
programming by "selection, not entry". That is, we select programming
constructs (by structure) rather than build the program as a string
of characters (symbolically). The mechanisms for selecting
construction schemas from the menu are thus related to Swinehart's
concept of "manipulative activity".
There are several difficulties involved in Hansen's system. His
system addressed itself too strictly to syntactic correctness. We see
the opportunity to extend this "selection, not entry" idea to aid
semantic correctness. It is currently feasible to associate a proof
construction with the program construction and thus give the
programmer added tools for construction of reliable programs.
In terms of the "manipulative activities", such a system has much to
offer. The command language will allow the programmer to present his
algorithms to a machine in terms more natural to himself. The
transition from idea to working program should be much easier. Since
the user need think less about programming details he should be able
to maintain a better grasp of his problem and thus, at the informal
level, be better prepared to construct a correct program. The
additional benefits of having an underlying formalism to reinforce
the informal feeling of correctness with a formal proof are exciting
indeed. Thus there are commands to manipulate the semantic
components of the programming being constructed. Formalisms do
currently exist which can become an appropriate basis for such a
command language. We will describe one such in the next section.
However, programming language semantics is in a early developmental
stage and we are not advocating a commitment to any school of
semantics. Our primary concern will be to show that a programming
style plus the computer-based mechanisms to support the pedagogy can
make a significant contribution to the quest for reliable software.
The mechanics of such an editing system clearly require the use of
display terminals. We envision a command language which will require
rapid display of program segments, rules of construction, partially
completed proofs, execution of program segments, modification of
program segments. Such behavior would not be feasible on other
devices.
Since little work has been done in this area, our first task is the
construction of a prototype system to demonstrate the style of program
construction which we are advocating. The specification language need
not be particularly sophisticated, but the experience with the tools
is of utmost necessity. Such a system should contain a simple
specification language, a simple command language for specifying
program constructions, and a transcript-commenting facility.
Such a system can be used for demonstration purposes, for
understanding what modifications or additions are called for, and
should certainly be useful in the development of succeeding systems.
We would expect to use this system in programming classes as soon as
by Spring term.
Applications of this programming environment to other educational
ventures are quite exciting. The applicability of a proper study of
abstract data structures and their algorithms extends far beyond
their applications as programming tools. We agree with K. Curtis:
"...it is time to start thinking about
teaching mathematics in the context of
computer science rather than teaching computer
science in the context of mathematics."
Indeed we would go much further. The ideas involved in abstract
algorithms extend far beyond applications to the teaching of
mathematics. Though the relevancy questions can be answered by
relating such material to programming, we are definitely not
advocating the teaching of programming in high schools. Rather
studying algorithms introduces ways of thinking, just as Geometry has
its primary goal to introduce axiomatics. We do not expect to produce
geometers; we should not expect to produce programmers.
Philosophically we can argue that data structures and algorithms are
fundamental disciplines, and pedagogically, we argue that such
computations are more natural and inviting than studying functions
People relate to algorithms better than to functions. The intuitive
motivation and reiforcement of realizablility on machines is
important. The lab we are proposing would be an integral part of our
study. Since we feel strongly that it is the underlying concepts,
rather than the surface properties of the programming language which
are proper material for study, we will develop a suitable text and
monitoring system to supplement the basic lab.
The systems programming and human engineering aspects must be
explored. We can easily imagine background facilities to do
consistency checking: correct calling sequences (data types, arity of
functions) Also, low level responses to questions about the program
or correctness proof should be attainable. We do not expect to build
a sophisticated knowledge-based system or to address the problems of
automatic programming. Such endeavors, we believe are premature. Our
philosophy is that of McCarthy: "In order for a program to be capable
of learning something it must first be capable of being told it."
Thus we would understand the programming process before attempting to
construct an automatic programmer. If our techniques are indeed
viable then this approach should lead to a more reasoned approach to
automatic programming. For then, the automatic construction of a
program is a machine-applied sequence of interactive programming
commands.
We see many extensions and applications for the ideas presented here
and are quite excited about their prospects.
Bibliography--(partial)
Swinehart, Daniel C., COPILOT: A Multiprocess Approach to Interactive
Programming Systems. PhD Thesis, Stanford University, AIM-230, July
1974
Hansen, Wilfred J., Creation of Hierarchic Text with a Computer
Display. PhD. Thesis, Stanford University, Argonne National Lab
Report# ANL-7818, July 1971
Low, James R., Automatic Coding: Choice of Data Strutures. PhD.
Thesis, Stanford University, AIM-242, August 1974.
Igarashi,S., London, R.L., & Luckham, D.C., Automatic Program
Verification I: A Logical Basis and its Implementation, Stanford
University, AIM-200, May 1973
Allen, C.D. & Jones, C.B., The Formal Development of an Algorithm,
IBM United Kingdom Laboratories, Hursley Park, UK, IBM Technical
Report TR.12.110, March 1973.
Cheatham, T.E., & Goldberg, J., Proceedings of a Symposium on the
High Cost of Software, Monterey, Cal, AD-777 121, September 1973
Buxton, J.N., & Randell, B., Software Engineering Techniques, Rome
Conference, April 1970.
Snowdon, R.A., Interactive Use of a Computer in the Preparation of
Structured Programs, PhD. Thesis, University of Newcastle Upon Tyne,
June 1974.
Allen, J.R., The Anatomy of a Language (tentative title) text book to
be published by McGraw-Hill.
Naur, P., Programming Languages, Natural Languages, and Mathematics.
SIGPLAN Palo Alto Conference Proceedings, 1975, pp137-148
Liskov, B. & Zilles, S. Specification Techniques for Data Abstraction.
Proceedings of the 1975 Conference on Reliable Software.
Curtis, Kent, K., Computer Science, Federal Programs, and Nirvana,
SIGCSE Bulletin, Vol. 7, No. 1, Feb 1975, pp109-113.
Weinberg, G.M., The Psychology of Computer Programming, Van Nostrand
Reinhold Co., New York (1971).
Mckeeman, W., On Preventing Programming Languages from Interfering with
Programming, IEEE Transactions on Software Engineering. 1975
Software Engineering
1968(Garmish) ed Naur & Randell
1969(Rome) ed Buxton & Randell
Ledgard, H., The case for Structured Programming, BIT Vol. 13,
pp.45-57. 1973
Winograd, T., Breaking the Complexity Barrier again, SIGPLAN-SIGIR
Interface Meeting, SIGPLAN Notices, Vol 10, No.1, Jan 1975, pp.13-30.
Gerhart, S., Correctness-Preserving Program Trnasformations. SIGPLAN
Palo Alto Conference Proceedings, 1975, pp54-66.
huet